// 分治 快排 数组划分、数组分块
// 使用 3 指针将数组分为 4 块：[0, left], [left + 1, cur], [cur, right - 1], [right, n - 1]
// [0, left] - left 维护的区间
// [left + 1, cur] - cur 维护的区间
// [cur, right - 1] - 待处理的区间
// [right, n - 1] - right 维护的区间
// cur 负责扫描数组

// 例题 1：
// 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，
// 使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
//
//        我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
//
//        必须在不使用库内置的 sort 函数的情况下解决这个问题。
//
//        示例 1：
//
//        输入：nums = [2,0,2,1,1,0]
//        输出：[0,0,1,1,2,2]
//        示例 2：
//
//        输入：nums = [2,0,1]
//        输出：[0,1,2]
//
//
//        提示：
//
//        n == nums.length
//        1 <= n <= 300
//        nums[i] 为 0、1 或 2
//
//
//        进阶：
//
//        你能想出一个仅使用常数空间的一趟扫描算法吗？

// 解题思路：
// 数组划分、数组分块
// 本质上还是将数组分块，可以参考霜双指针章节的第一个题目
// 这道题需要将三种颜色分开，使用 双指针 的算法也能解决这个问题，需要遍历数组两遍，每次维护一种颜色，时间复杂度 O(n2)
// 使用三指针则是每个指针维护一个颜色，遍历一次就可以将颜色排好，时间复杂度 O(n)

public class SortColors {
    // 解法 1：三指针（快速排序思想）
    public void sortColors1(int[] nums) {
        int n = nums.length;
        int cur = 0;
        int left = -1; int right = n;
        while(cur < right){
            if(nums[cur] == 0){
                int tmp = nums[++left];
                nums[left] = nums[cur];
                nums[cur] = tmp;
                cur++;
            }else if(nums[cur] == 2){
                int tmp = nums[--right];
                nums[right] = nums[cur];
                nums[cur] = tmp;
            }else cur++;
        }
    }
    //解法 2：双指针
    public void sortColors2(int[] nums) {
        int n = nums.length;
        if(n == 1) return;
        int left = -1; int right = 0;
        while(right < n){
            if(left < right && nums[right] == 0){
                int tmp = nums[left + 1];
                nums[left + 1] = nums[right];
                nums[right] = tmp;
                left++;
            }else right++;
        }
        right = left + 1;
        while(right < n){
            if(left < right && nums[right] == 1){
                int tmp = nums[left + 1];
                nums[left + 1] = nums[right];
                nums[right] = tmp;
                left++;
            }else right++;
        }
    }
}
